package 力扣._234_回文链表;


public class Solution {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public boolean isPalindrome(ListNode head) {
        ListNode t = head;
        ListNode mid = head;
        ListNode former = new ListNode(); //前一半链表,补上头结点
        former.next = null;
        //先判断长度
        int len = 0;
        while (t != null) {
            len++;
            t = t.next;
        }
        //利用头插法将前一半链表逆置
        for (int i = 0; i < len / 2; i++) {
            t = mid;
            mid = mid.next;
            t.next = former.next;
            former.next = t;
        }
        //将前半链表与后半链表挨个比较
        if (len % 2 == 1)
            mid = mid.next;
        former = former.next;
        while (mid != null && former != null) {
            if (mid.val != former.val)
                return false;
            mid = mid.next;
            former = former.next;
        }
        return true;
    }

    public static void main(String[] args) {

    }
}